package com.github.hgkmail.hello.leetcode101.collection.array;

//从右上角开始搜索
//使用visited全局状态变量来避免走重复的格子
//todo 两次二分查找的写法：binarySearchFirstColumn、binarySearchRow
//二分查找写法：左闭右开、左闭右闭
public class LC74SearchA2dMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length;
        int n=matrix[0].length;
        //base
        if (m<=0 || n<=0) {
            return false;
        }
        //global
        boolean[][] visited = new boolean[m][n]; //boolean动态数组默认值为false
        //右上角
        int i=0;
        int j=n-1;
        while (i>=0 && i<m && j>=0 && j<n) {
            if (visited[i][j]) {
                //重复的格子，说明搜不到
                break;
            }
            visited[i][j]=true;
            if (matrix[i][j]==target) {
                return true;
            } else if (matrix[i][j]>target) { //变小
                if (j<=0) {
                    //跳到上一行末尾
                    i--;
                    j=n-1;
                } else {
                    j--;
                }
            } else { //变大
                if (j>=n-1) {
                    //跳到下一行开头
                    i++;
                    j=0;
                } else {
                    j++;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {

    }
}
